import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> deque = new ArrayDeque<>();
        List<List<Integer>> ret = new ArrayList<>();
        boolean flag = false;
        if (root == null) return ret;
        deque.add(root);
        while (!deque.isEmpty()) {
            int size = deque.size(); // 当前层的节点数量
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode n = deque.poll();
                tmp.add(n.val);
                if (n.left != null) {
                    deque.add(n.left);
                }
                if (n.right != null) {
                    deque.add(n.right);
                }
            }
            if (flag) {
                Collections.reverse(tmp);
            }
            flag = !flag;
            ret.add(tmp);
        }
        return ret;
    }
}